non-deterministic polynomial

non-deterministic polynomial
Математика: недетерминированный полиномиальный

Универсальный англо-русский словарь. . 2011.

Игры ⚽ Нужно решить контрольную?

Смотреть что такое "non-deterministic polynomial" в других словарях:

  • Non-deterministic Turing machine — Turing machine(s) Machina Universal Turing machine Alternating Turing machine Quantum Turing machine Read only Turing machine Read only right moving Turing Machines Probabilistic Turing machine Multi track Turing machine Turing machine… …   Wikipedia

  • Polynomial time — In computational complexity theory, polynomial time refers to the computation time of a problem where the run time, m ( n ), is no greater than a polynomial function of the problem size, n .Written mathematically using big O notation, this states …   Wikipedia

  • Polynomial space — In computational complexity theory, polynomial space refers to the space required in computation of a problem where the space, m ( n ), is no greater than a polynomial function of the problem size, n .Written mathematically, m ( n ) = O( n k )… …   Wikipedia

  • Machine de Turing non déterministe — Une machine de Turing non déterministe ressemble à une machine de Turing habituelle, c est à dire déterministe, mais elle diffère d elle en ce qu elle peut avoir, pour un état donné, plusieurs transitions activables. Sommaire 1 Présentation… …   Wikipédia en Français

  • Schwartz-Zippel lemma and testing polynomial identities — Polynomial identity testing is the problem of determining whether a given multivariate polynomial is the0 polynomial or identically equal to 0. The input to the problem is an n variable polynomial over a fieldF. It can occur in the following… …   Wikipedia

  • Polynomial-time reduction — In computational complexity theory a polynomial time reduction is a reduction which is computable by a deterministic Turing machine in polynomial time. If it is a many one reduction, it is called a polynomial time many one reduction, polynomial… …   Wikipedia

  • NP-hard — For a gentler introduction, see P versus NP problem. Euler diagram for P, NP, NP complete, and NP hard set of problems NP hard (non deterministic polynomial time hard), in computational complexity theory, is a class of problems that are,… …   Wikipedia

  • UP (complexity) — In complexity theory, UP ( Unambiguous Non deterministic Polynomial time ) is the complexity class of decision problems solvable in polynomial time on a non deterministic Turing machine with at most one accepting path for each input. UP contains… …   Wikipedia

  • Arthur–Merlin protocol — In computational complexity theory, an Arthur–Merlin protocol is an interactive proof system in which the verifier s coin tosses are constrained to be public (i.e. known to the prover too). This notion was introduced by Babai (1985). Goldwasser… …   Wikipedia

  • Advice (complexity) — Advice is a concept in complexity theory. An advice string is an extra input to a Turing machine which is allowed to depend on the length n of the input, but not on input itself. A decision problem is in the complexity class P/f(n) if there is a… …   Wikipedia

  • NP — noun Abbreviation of non deterministic polynomial ; the complexity class of computational problems that a non deterministic Turing machine can solve in polynomial time. See Also: NP complete, NP hard …   Wiktionary


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»